﻿using System;
using System.Collections.Generic;
using System.Text;

namespace GA
{
    public class Combinatorics
    {
        // following function is due to MSDN
        /// <summary>
        /// Find kth lexical permutation of length n
        /// </summary>
        public static int[] Permutation(int n, decimal k)
        {
            int[] data = new int[n];
            int order = data.Length;

            // Step #1 - Find factoradic of k
            int[] factoradic = new int[n];

            for (int j = 1; j <= n; ++j)
            {
                factoradic[n - j] = (int)(k % j);
                k /= j;
            }

            // Step #2 - Convert factoradic to permutation
            int[] temp = new int[n];

            for (int i = 0; i < n; ++i)
            {
                temp[i] = ++factoradic[i];
            }

            data[n - 1] = 1;  // right-most element is set to 1.

            for (int i = n - 2; i >= 0; --i)
            {
                data[i] = temp[i];
                for (int j = i + 1; j < n; ++j)
                {
                    if (data[j] >= data[i])
                        ++data[j];
                }
            }

            for (int i = 0; i < n; ++i)  // put in 0-based form
            {
                --data[i];
            }
            return data;

        }  // Permutation(n,k)

        private static Dictionary<decimal, decimal> _factorials = new Dictionary<decimal, decimal>();
        public static decimal fact(decimal n)
        {
            if (n <= 2)
                return n;

            if (!_factorials.ContainsKey(n))
            {
                _factorials.Add(n, n * fact(n - 1));
            }

            return _factorials[n];
        }
    }

}
